The invention is based on a priority application DE 101 57 103.8 which is hereby incorporated by reference.
The present invention relates to a procedure for the allocation of time slots for a transmission of data in variable time slots between a controller of a packet-oriented data network on the one hand and a terminal of a user of the data network on the other hand. The time slots for the data transmission are assigned to a terminal for a data flow following request made by the terminal and in dependence on the transmission capacity available in the data network, and temporarily stored in a ring buffer before they are allocated to the terminal at a predefinable allocation instant.
The invention also relates to a controller for a packet-oriented data network for the transmission of data in variable time slots between the controller on the one hand and a terminal of a user of the data network on the other hand. The controller comprises means for receiving and processing a request made by a terminal for time slots, and means for allocating time slots upon the request made by the terminal. The means for allocation assign the time slots to a terminal in dependence on the transmission capacity available in the data network, and temporarily store the assigned time slots in a ring buffer before the means for allocation allocate the time slots to the terminal at a predefinable allocation instant.
Finally, the present invention also relates to a computer program which can be executed on a computing device, particularly on a microprocessor, of a controller for a packet-oriented data network for the transmission of data in variable time slots.
The data rate available in a data network is determined primarily by the minimum data rate agreed between providers and users (the so-called service level agreement). The available data rate is determined, secondly, by the instantaneous capacity utilization of the data network by data transmission connections. For the use of the data network, the user normally makes a payment to the provider which is dependent on the agreed data rate.
A terminal seeking to transmit data via the data network sends a request for one or more time slots to a controller of the data network. Depending on the availability of time slots or depending on the capacity utilization of the data network, the controller allocates the requested number or fewer time slots to the terminal. In the case of a very high capacity utilization, it may even be the case that the controller is unable to fulfil the request made by the terminal, rejects it and does not allocate any time slots to it whatsoever. The rejected request made by the terminal is stored in a queue (e.g. in a first-in-first-out (FIFO) memory) of the controller and fulfilled at a later instant, at which there is a lesser capacity utilization of the data network, in that time slots which have been requested but not yet allocated are then allocated to the terminal. The requesting terminal and the data flow for which time slots are requested, as well as the number of requested time slots, must be stored in the queue. In addition, a corresponding time stamp must be assigned to each request. The storage of the rejected requests in the queue can be very memory-intensive. If a queue is full, new requests are lost.
Known from the prior art, therefore, for the allocation of time slots, is the practice of taking into account, at the start of a new data transmission, the capacity utilization of the data network as a whole and the bandwidth available on the data network. Once a certain number of time slots have been allocated to a terminal for the data transmission, the user may transmit his data in these time slots even if this data transmission occupies the entire transmission capacity of the data network or a major part of this capacity. During this time, requests for time slots made by other terminals may not be completely fulfilled, or not fulfilled at all. Wait times may occur before the further terminals are serviced. Thus, for the data transmissions of the further terminals, it is not possible to guarantee a minimum response time within which the requested time slots, or a minimum number of time slots, can be assigned to the terminals. This can present substantial problems for applications in which a minimum response time and a minimum data transmission rate must be assured. Such applications are also termed QoS (quality of service) applications. Examples of QoS applications are VoIP (Voice over Internet Protocol) applications.
In the case of so-called Transfer Control Protocol (TCP)/IP applications, the data transmission commences at a relatively low data rate. During a data transmission, the quality of the data transmission is monitored and, if this fulfils a predefinable minimum quality requirement, continuously increased until the minimum requirement is no longer fulfilled. The data transmission rate is then reduced again to the relatively low starting value and slowly increased again. Thus, if the quality of a TCP/IP data transmission so permits, such a data transmission may occupy a major part of the bandwidth available in a data network. In addition, a TCP/IP data transmission can result in a substantial fluctuation of the network capacity utilization. This can be a major disturbance factor for QoS applications.
The procedure according to the invention is applicable to all packet-oriented data networks in which the award of time slots for data transmission must be negotiated between the terminals and the controller.
The data network is designed as, for example, a cable television network via which video and audio data is transmitted according to a predefinable standard. The standard renders possible a data transmission according to the procedure of the initially stated type. A concrete example of such a standard is DVB (Digital Video Broadcasting), which is used primarily in Europe, or DOCSIS (Data Over Cable Service Interface Specification), which is used particularly in the USA. DVB uses a fixed time pattern of, for example, three milliseconds, with 9, 18 or 36 time slots being transmitted per time pattern. In DVB, the two lowest layers of the ISO/OSI layer model are specified, namely, the physical layer and the Media Access Control (MAC) layer, or link layer.
In recent times, increasingly more households have been receiving television signals, no longer via television antennae or satellites, but via a cable television network. In this case, a television transmitter transmits video and audio signals to television sets in the households, over several channels in a television broadcast band, via a so-called combiner, which substantially comprises a frequency multiplexer, and via the cable television network. In order that the cable television network can also be used for QoS applications, a switching device (a so-called router) is provided which is connected to the Internet. The router is additionally connected, via a bidirectional connection, to a controller of the network, a so-called interactive network adapter (INA) which, in turn, is likewise connected to the combiner via a bidirectional connection. The router and the INA can be combined in one device. The terminals for the QoS applications in a household are connected to the cable television network via so-called set-top boxes or so-called cable modems. Thus, the combiner transmits both the video and audio signals of the television transmitter and the data from the Internet into the households, where they are distributed to the appropriate terminals. For example, the video and audio signals are forwarded to a television set and the Internet data is forwarded to a computer. For VoIP applications, the computer is equipped with appropriate add-on modules which permit the output and input of speech.
Also provided as standard in the cable television network are upstream channels which render possible a so-called upstream connection of the terminals to the INA. In comparison with the downstream channels, however, the upstream channels have only a small bandwidth. For certain data applications, however, relatively large amounts of data are also transmitted via the upstream channel. In addition, it must be possible for a certain quality of data transmission to be guaranteed via the upstream channel (e.g., for QoS applications). The quality of a data transmission comprises, in particular, a predefinable minimum transmission rate, a limited delay time (i.e., transmission time of the individual data packets transmitted in the time slots) and a limited jitter (i.e. variation of the transmission time of the individual transmitted data packets).
The operation of controlling and coordinating a data transmission comprises the so-called policing (i.e. the allocation of a limited number of time slots to the individual data flows in order to achieve a required data rate) and the so-called shaping (i.e. the allocation of time slots for optimum exploitation of the bandwidth available in the network). In cable television networks, the upstream channel, due to its small bandwidth, constitutes a bottleneck for the transmission of data. If functions such as policing and shaping are first executed, in a so-called access router of the data network, in the third from bottom layer, the so-called IP layer, of the ISO/OSI layer model, the transmitted data packets have already passed the bottleneck. If, within the scope of the policing and shaping in the access router, data packets already transmitted via the upstream channel were to be dropped, this represents a loss of bandwidth.
The use of ring buffers as queues is known from the prior art (e.g. from EP 1 056 244 A2). The ring buffer revolves at a predefinable clock rate. The known ring buffers have a write pointer and a read pointer which respectively point to (temporally) determined write and read positions in the ring buffer. The ring buffer thus revolves relative to the read and write position so that, following a complete revolution of the ring buffer, each field has been once at the write position and once at the read position.
Such a known ring buffer, however, cannot be used for the allocation of variable time slots for a data transmission in a packet-oriented data network. In this case, data flows with varying allocation instants may be processed. A first processed data flow has an allocation instant in, for example, 30 ms, the next processed data flow has an allocation instant in, for example, 28 ms and the next processed data flow, in turn, has an allocation instant in, for example, 32 ms. It is therefore necessary for the write pointer and/or the read pointer to be (temporally) variable, so that the time slots assigned to a terminal for the data flow can be stored in the appropriate field of the ring buffer in dependence on the exact allocation instant of each data flow.